Field of the Invention
The invention relates to a network device, and in particular, to a network device applying a hash memory architecture supporting longest prefix matching (LPM).
Description of the Related Art
As the number of devices connected to data networks increases and higher data rates are required, there is a growing need for new technologies that enable higher transmission rates. In this regard, various efforts exist, including technologies that enable transmission rates that may even exceed Gigabits-per-second (Gbps) data rates. For example, the IEEE 802.3 standard defines the (Medium Access Control) MAC interface and physical layer (PHY) for Ethernet connections at 10 Mbps, 100 Mbps, 1 Gbps, and 10 Gbps data rates over twisted-pair copper cabling. Accordingly, as data rates increase due to widespread deployment of 1 Gbps and 10 Gbps Ethernet switches, fast IP address lookups have become indispensable for core and edge routers. Meanwhile, the number of prefixes in core routers has experienced explosive growth. Earlier solutions to IP address lookups were tries-based through software execution to match an IP address progressively a few bits at a time. In this regard, prefixes were stored in a tree-like data structure to support longest prefix matching (LPM), which chooses the longest prefix among those which match the given IP address.
In contrast, hash tables offer an attractive method for fast IP lookups because of their constant-time search latencies. Hash tables are also attractive because they can be implemented in regular SRAM. SRAM is less expensive, more energy efficient, and exhibits higher densities than TCAM. However, hash tables cannot record entries having “don't care” bits, and data collisions may occur in hash tables. Accordingly, it would be less efficient to use hash tables only while performing IP lookups.